package cn.nawang.ebeim.client.version;

import org.apache.commons.io.IOUtils;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Created by GanJc on 2016/2/25.
 */
public class LargestRectangleInHistogram {

    public static void main(String[] args) {
        int a[] = {2, 1, 5, 6, 2, 3};
        LargestRectangleInHistogram(a);//10
        int b[] = {2, 1, 4, 5, 6, 2, 3};
        LargestRectangleInHistogram(b);//12
        int c[] = {5,6,7,8,3};
        LargestRectangleInHistogram(c);//20


        System.out.println("-------------");
        LargestRectangleInHistogram2(a);
        LargestRectangleInHistogram2(b);
        LargestRectangleInHistogram2(c);
        int d[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
        LargestRectangleInHistogram2(d);

    }

    //不是最优解 时间超出限制
    public static void LargestRectangleInHistogram(int[] a) {
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            int now = a[i];
            int count = 1;

            int r = i + 1;
            int l = i - 1;

            while (r < a.length - 1 && a[r] >= now) {
                r++;
                count++;
            }

            while (l > 0 && a[l] >= now) {
                l--;
                count++;
            }

            if (now * count > max) {
                max = now * count;
            }
        }
        System.out.println(max);
    }

    //o(n)解，利用栈压榨时间复杂度
    public static void LargestRectangleInHistogram2(int[] a) {
        //数组末位补零
        int b[] = new int[a.length + 1];
        System.arraycopy(a, 0, b, 0, a.length);
        Stack<Integer> s = new Stack();
        int sum = 0;
        for (int i = 0; i < b.length; i++) {
            if (s.empty() || b[i] > b[s.peek()]) { //和栈顶比较
                s.push(i);
            } else {
                int t = s.pop();//弹出
                //这里还需要考虑stack为空的情况
                int width = i;
                if(!s.isEmpty()){
                    width = i - s.peek() - 1 ;
                }
                int max = b[t] * width;
                if (max > sum) {
                    sum = max;
                }
                i--;
            }
        }
        System.out.println(sum);
    }

}
